#include<cstdio>
#include<cstdlib>
#define LL long long
LL gcd(LL a,LL b)	//计算最大公约数
{
	if(a<b)
		return gcd(b,a);
	return b?gcd(b,a%b):a;
}
LL fabs(LL a)	//求绝对值
{
	return a<0?-a:a;
}
LL qkc(LL a,LL q,LL Mod)
{
    LL ans=0;
    while(q)
    {
        if(q & 1)
            ans = (ans + a) % Mod;
        q >>=1;
        a = (a<<1) %Mod;
    }
    return ans;
}
LL qkpow(LL a,LL q,LL Mod)
{
    LL ans=1;
    while(q)
    {
        if(q & 1)
            ans = qkc(ans,a,Mod);
        q >>=1;
        a = qkc(a,a,Mod);
    }
    return ans;
}
bool Miller_Rabin(LL n)
{
    if(n==46856248255981ll || n<2)
        return false;
    if(n==2 || n==3 || n==7 || n==61 || n==24251)
        return true;
    if(n < 2 || !(n & 1))
        return 0;
    LL k = 0,f = n-1,pre,x;
    while(f % 2 == 0)
    {
        k ++;
        f >>= 1;
    }
    for(int i = 1;i <= 9;i ++)
    {
        x = rand() % (n - 2) + 2;
        x = qkpow(x,f,n);
        pre = x;
        for(int j = 1;j <= k;j ++)
        {
        	x = qkc(x,x,n);
        	if(x == 1 && pre != 1 && pre != n-1)
        		return 0;
        	pre=x;
		}
		if(x!=1)
			return 0;
    }
    return 1;
}
LL t,n;
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        if(Miller_Rabin(n))
            puts("Yes");
        else
            puts("No");
    }
}
